package com.lanxincn.touye.external.struct;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 有向图
 */
public class Graph {

    private static final int INFINITE = -1;//代表无穷，路径不可达

    private static final int MaxNum = 100;//图的最大顶点数

    private int nodeNum;//顶点数量

    private int edgeNum;   //边的数量

    private Node[] vertex = new Node[MaxNum]; //保存顶点信息

    private int[][] edgeWeight = new int[MaxNum][MaxNum];//保存权

    private Map<Node, Path> pathMap = new HashMap<>();

    /**
     * 添加节点
     */
    public void addNode(Node node) {
        this.vertex[nodeNum++] = node;
        for (int i = 0; i < nodeNum - 1; i++) {
            this.edgeWeight[nodeNum - 1][i] = INFINITE;
            this.edgeWeight[i][nodeNum - 1] = INFINITE;
        }
    }


    /**
     * 添加有向边
     */
    public void addEdge(Node start, Node end, int weight) {
        int i = -1;
        int j = -1;
        for (int k = 0; k < this.nodeNum; k++) {
            Node vx = vertex[k];
            if (vx.equals(start)) {
                i = k;
            }
            if (vx.equals(end)) {
                j = k;
            }
        }
        if (i != -1 && j != -1) {
            edgeWeight[i][j] = weight;
            edgeNum++;
        }
    }


    /**
     * 获得最短路径
     */
    public List<Node> getPath(Node start, Node end) throws PathNotAccessException {
        if (this.pathMap.containsKey(start)) {
            Path path = this.pathMap.get(start);
            for (int i = 0; i < nodeNum; i++) {
                if (vertex[i].equals(end)) {
                    return path.getPath(i);
                }
            }
        } else {
            for (int i = 0; i < nodeNum; i++) {
                if (vertex[i].equals(start)) {
                    Path path = dijkstra(i);
                    this.pathMap.put(vertex[i], path);
                    for (int j = 0; j < nodeNum; j++) {
                        if (vertex[j].equals(end)) {
                            return path.getPath(j);
                        }
                    }
                }
            }
        }
        return null;
    }

    /**
     * 获得最短路径ids
     */
    public List<Integer> getPathIds(Node start, Node end) throws PathNotAccessException {
        List<Node> path = getPath(start, end);
        if (path != null) {
            return path.stream().map(Node::getId).collect(Collectors.toList());
        }
        return null;
    }


    /**
     * 打印矩阵
     */
    public void print() {
        for (int i = 0; i < nodeNum; i++) {
            if (i == 0) {
                for (int j = 0; j < nodeNum; j++) {
                    if (j == 0) {
                        System.out.printf("%5s", "");
                    }
                    System.out.printf("%5s", "v" + (j + 1));
                }
                System.out.println();
            }
            for (int j = 0; j < nodeNum; j++) {
                if (j == 0) {
                    System.out.printf("%5s", "v" + (i + 1));
                }
                System.out.printf("%5s", edgeWeight[i][j] == -1 ? "∞" : edgeWeight[i][j]);
            }
            System.out.println();
        }
    }

    /**
     * 迪杰斯特拉算法
     */
    private Path dijkstra(int vs) {
        boolean[] flag = new boolean[nodeNum];
        int[] distance = new int[nodeNum];

        String[] path = new String[nodeNum];

        for (int i = 0; i < nodeNum; i++) {
            distance[i] = edgeWeight[vs][i];
        }

        for (int i = 0; i < nodeNum; i++) {
            path[i] = vs + "";
        }

        //初始化
        flag[vs] = true;

        for (int k = 0; k < nodeNum; k++) {

            int min = -1;
            int index = -1;
            for (int i = 0; i < nodeNum; i++) {
                if (!flag[i] && (min == -1 || (distance[i] != -1) && (distance[i] < min))) {
                    min = distance[i];
                    index = i;
                }
            }
            if (index != -1) {
                flag[index] = true;
                path[index] = path[index] + "," + index;
                for (int i = 0; i < nodeNum; i++) {
                    if (!flag[i] && (min != -1 && edgeWeight[index][i] != -1 && (distance[i] == -1 || distance[i] > min + edgeWeight[index][i]))) {
                        distance[i] = edgeWeight[index][i] + min;
                        path[i] = path[index];
                    }
                }
            }
        }
        return new Path(vertex[vs], path, distance);
    }


    /**
     * 路径
     */
    private class Path {

        //起点
        private Node origin;

        //路径字符串
        private String[] pathString;

        //路径节点
        private List<List<Node>> path;

        //路径距离
        private int[] distance;

        public Path(Node origin, String[] pathString, int[] distance) {
            this.origin = origin;
            this.pathString = pathString;
            this.distance = distance;
            init();
        }

        private void init() {
            ArrayList<List<Node>> path = new ArrayList<>();
            for (String s : pathString) {
                List<String> strings = Arrays.asList(s.split(","));
                ArrayList<Node> nodes = new ArrayList<>();
                strings.forEach(e -> {
                    Node node = vertex[Integer.parseInt(e)];
                    nodes.add(node);
                });
                path.add(nodes);
            }
            this.path = path;
        }

        public boolean accessible(int index) {
            if (this.distance != null && this.distance.length > index) {
                return this.distance[index] != -1;
            }
            return false;
        }

        public List<Node> getPath(int index) throws PathNotAccessException {
            if (accessible(index)) {
                return this.path.get(index);
            }
            throw new PathNotAccessException();
        }

    }

    public static void main(String[] args) throws PathNotAccessException {
        Graph graph = new Graph();
        Node node1 = new Node(1, "v1");
        Node node2 = new Node(2, "v2");
        Node node3 = new Node(3, "v3");
        Node node4 = new Node(4, "v4");
        Node node5 = new Node(5, "v5");
        Node node6 = new Node(6, "v6");
        Node node7 = new Node(7, "v7");
        Node node8 = new Node(8, "v8");
        graph.addNode(node1);
        graph.addNode(node2);
        graph.addNode(node3);
        graph.addNode(node4);
        graph.addNode(node5);
        graph.addNode(node6);
        graph.addNode(node7);
        graph.addNode(node8);
        graph.addEdge(node1, node2, 1);
        graph.addEdge(node2, node3, 1);
        graph.addEdge(node3, node4, 1);
        graph.addEdge(node3, node6, 1);
        graph.addEdge(node4, node5, 1);
        graph.addEdge(node5, node6, 1);
        graph.addEdge(node6, node7, 1);
        graph.addEdge(node7, node8, 1);
        graph.addEdge(node1, node8, 1);
        graph.addEdge(node8, node1, 1);

        graph.print();
    }


}
